package Top_Interview_Questions_Review._009Linked_List;


import Top_Interview_Questions_Review.ListNode;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/10 17:35
 * <p>
 * 功能描述:
 */
public class _0160 {

    /**
     *  题解：设链表A的长度为a+c，链表B的长度为b+c，a为链表A不公共部分，b为链表B不公共部分，
     *      c为链表A、B的公共部分
     *     将两个链表连起来，A->B和B->A，长度：a+c+b+c=b+c+a+c，
     *     1.若链表AB相交，则a+c+b与b+c+a就会抵消，它们就会在c处相遇；
     *     2.若不相交，则c为nullptr，则a+b=b+a，它们各自移动到尾部循环结束，即返回nullptr
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}
